//  https://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7da?tpId=46&tqId=29060&tPage=2&rp=2&ru=/ta/leetcode&qru=/ta/leetcode/question-rankin
public class Solution {
    //三角矩阵
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.size() == 0) {
            return 0;
        }
        int row = triangle.size();
        for (int i = 1; i < row; i++) {
            for (int j = 0; j <= i; j++) {
                int ret = triangle.get(i).get(j);
                if (j == 0) {
                    triangle.get(i).set(j, triangle.get(i - 1).get(j) + ret);
                } else if (j == i) {
                    triangle.get(i).set(j, triangle.get(i - 1).get(j - 1) + ret);
                } else {
                    int value = Math.min(triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1));
                    triangle.get(i).set(j, value + ret);
                }
            }
        }
        ArrayList<Integer> list = triangle.get(row - 1);
        int minValue = list.get(0);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) < minValue) {
                minValue = list.get(i);
            }
        }
        return minValue;
    }

    //自上往下
    public int minimumTotal1(ArrayList<ArrayList<Integer>> triangle) {
        int row = triangle.size();
        int col = triangle.get(row - 1).size();
        int[][] array = new int[row][col];
        array[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < row; i++) {
            for (int j = 0; j <= i; j++) {
                int value = triangle.get(i).get(j);
                if (j == 0) {
                    array[i][j] = array[i - 1][j] + value;
                } else if (j == i) {
                    array[i][j] = array[i - 1][j - 1] + value;
                } else {
                    array[i][j] = min(array[i - 1][j], array[i - 1][j - 1]) + value;
                }
            }
        }
        int minValue = array[row - 1][0];
        for (int i = 0; i < col; i++) {
            if (minValue > array[row - 1][i]) {
                minValue = array[row - 1][i];
            }
        }
        return minValue;
    }

    /*
     * //自下往上
     *
     *
     * */
    public int minimumTotal2(ArrayList<ArrayList<Integer>> triangle) {
        int row = triangle.size();
        int col = triangle.get(row - 1).size();
        int[][] array = new int[row][col];
        for (int i = 0; i < col; i++) {
            array[row - 1][i] = triangle.get(row - 1).get(i);
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                array[i][j] = min(array[i + 1][j], array[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return array[0][0];
    }

    /*
     * //一个数组搞定
     *
     * */
    public int minimumTotal21(ArrayList<ArrayList<Integer>> triangle) {
        int row = triangle.size();
        int col = triangle.get(row - 1).size();
        int[] array = new int[col];
        for (int i = 0; i < col; i++) {
            array[i] = triangle.get(row - 1).get(i);
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                int value = triangle.get(i).get(j);
                array[j] = min(array[j], array[j + 1]) + value;
            }
        }
        return array[0];
    }
}